Today's information age has experienced a tremendous growth in the volume of data communicated over various networks. For example, enormous amounts of data are transferred every day between computers connected by data networks like intra-nets, internet, local area nets, wide area nets, etc. The speed by which these data are communicated, i.e., data throughput, is an important consideration in a data network. Of course, the network's data throughput is proportional to the amount of communication resources allocated for communicating data, with more allocated resources resulting in a higher data throughput. Since the communication resources are scarce, many networks share these resources among many users.
Another important consideration is a network's overall communication error rate, with some networks requiring residual error rates of less than 10.sup.-16. Some communication networks use packet-switched communication links in which the user information is packetized, and the packets are individually sent as data burst from a source to a destination. In packet-switched networks, the data throughput is expressed in terms of the number of data packets per unit of time. Since the links are not perfect, especially when wireless links are used, the error rate requirement is not easily met unless some type of error correction mechanism is introduced, for correcting errors while data is being communicated over the network.
Error correction schemes can be divided into two classes: a forward-error-correction (FEC) method, and a retransmission method. In the FEC method, extra coding bits are added at the source to increase the redundancy in the information. This extra redundancy will enable the destination to correct errors. In the retransmission method, extra check bits are added to the data packets at the source so that the destination can check the data packets for errors. If the destination detects an error, it will automatically request for a retransmission of the data packet. This type of retransmission method is known as Automatic Retransmit Query (ARQ) method.
The data traffic over a switched packet network is carried out in data bursts. Communication errors often arrive in bursts as well. Therefore, it is more efficient to apply a ARQ method, which requires occasional retransmissions, than to apply FEC coding, which adds a constant overhead irrespective of whether there are communication errors or not. A slight amount of FEC coding is always advantageous to avoid retransmissions of data packets that have very few errors. Accordingly, the use of an ARQ method, preferably, with little FEC, is necessary in order to produce a low residual error rate in a high data throughput network.
A number of ARQ methods is known. In general, the ARQ methods may be divided into a numbered ARQ method and an unnumbered ARQ method. In the numbered ARQ method, each data packet is assigned a packet number that allows the destination to specify which data packets have arrived successfully and which have arrived erroneously. In this way, the data packets do not have to arrive at the destination in the order of transmission from the source. As is well known, the packet-switched networks transfer consecutive packets along different paths having different delays. Therefore, the data packets may arrive out of sequence. By using the packet numbers of the numbered ARQ method, the data packets can be reordered at the destination in proper sequence.
In the unnumbered ARQ method, packets do not carry a packet number. Therefore, the unnumbered ARQ method requires less overhead and, thus, is less complex to implement. In order to avoid out-of-order arrival of data packets, however, the data packets must be communicated in an orderly manner. A well-known unnumbered ARQ method is a stop-and-wait ARQ method in which the source stops and waits until a transmitted data packet is acknowledged. For each data packet, a positive acknowledgement (ACK) must be received from the destination, before a subsequent data packet can be transmitted from the source. If a negative acknowledgement (NAK) is received from the destination, however, the source retransmits the same data packet again. If no acknowledgement is received, the source will automatically retransmit the same data packet after a timeout period.
The delay between the data packet transmission and the arrival of the acknowledgement information is known as a round-trip delay. The round-trip delay determines the data throughput of the network. The longer the round-trip delay, the longer the source has to wait before it can transmit a new data packet or retransmit a NAKed data packet. Accordingly, the data throughput on the communication link is inversely proportional to the round-trip delay between the source and destination. Because during the wait periods, the source is idle and no transmission takes place, in order to maintain a high data throughput, the stop-and-wait ARQ methods are generally used in networks with short round-trip delays.
FIG. 1 shows an exemplary timing diagram of a data packet transfer that uses a conventional stop-and-wait ARQ method. As shown, a sequence of five (5) data packets are transmitted from a source 12 to a destination 14. The data packet are shown by numbers 1 to 5 for illustration purpose only. In practice, however, no number is assigned to the data packets. The round trip delay between a packet and its response is shown by T.sub.d. If a data packet is not received successfully, the destination 14 transmits a NAK to the source. For example, an erroneously transmitted 3rd data packet, shown by number 3 in FIG. 1, is retransmitted from the source 12 during the next transmission based on a NAK received from the destination 14. Assuming that there are no errors in the returned acknowledgement information, only data packets that have failed during a transmission are retransmitted. Accordingly, the stop-and-wait ARQ method makes efficient use of the communication resource by allowing for sharing of communication resources among users during idle times. Moreover, the data packets arrive at the destination 14 in the order of transmission from the source 12. Thus, under the stop-and-wait ARQ method, there is no need for numbering and reordering of the data packets, which significantly reduces communication overhead.
As described above, if the available communication resource are efficiently allocated, the stop-and-wait ARQ method provides a high overall data throughput. Because of acknowledgment requirement, however, the data throughput per user may be low under the stop-and-wait ARQ method. Although attractive because of its simplicity and resource efficiency, the stop-and-wait ARQ method is less attractive in high-speed networks, especially when the round-trip delay increases.
In order to provide high per user data throughput, most modern data links use the numbered ARQ method. Under this method, a higher data throughput is resulted because of the ability to communicate new data packets before preceding data packets are acknowledged. A well-known numbered ARQ method is go-back-N ARQ method in which each data packet is numbered. In the conventional go-back-N ARQ method, the source uses a rotating N-element buffer containing N data packets, for example, packets k to k+N. The N packets of the buffer are subsequently transmitted. When the source is back at frame k, the source determines whether the corresponding data packet has been acknowledged. If so, the source transmits frame k+N+1. If not, the source transmits the entire buffer contents, including frames k to k+N again. For optimal performance, the buffer length (or the repetition period of the retransmissions) spans over a longer time period than the longest round-trip delay. The go-back-N ARQ method provides a higher throughput per user since the source does not have to wait for an acknowledgement before it can transmit the next data packet. However, the go-back-N ARQ scheme is less efficient from a shared resource point of view, since a single data packet failure results in the retransmission of all data packets in the buffer.
Better performance is obtained with a cumulative go-back-N ARQ method, which is a modified version of the ordinary go-back-N method. In the cumulative method, the destination stores all successfully received data packets, and acknowledges the highest packet number of the data packets received in sequence. This allows the destination to jump over a number of data packets in a rotating buffer if they correspond to data packets with a lower number than the highest packet number the destination indicates. In addition, data packets that have been successfully received once but failed during a retransmission, do not have to be retransmitted again. Although less so than ordinary go-back-N ARQ method, the cumulative method does not prevent the retransmission of successfully received data packets. The buffer lengths in both of these methods depend on the round-trip delay. As in the stop-and-wait ARQ method, the data throughput decreases, when the round-trip delay increases, but only in an error prone environment. Under error free conditions, optimal throughput is obtained.
The most efficient ARQ scheme, both with respect to throughput per user and shared resource efficiency is a selective repeat ARQ method. According to this method, the destination specifies in the acknowledgement exactly which data packet has to be retransmitted. In this way, only failed packets are retransmitted, and no packet transmission is delayed due to a retransmission. The packet numbers are used both for retransmission requests and for the ordering of out-of-sequence data packets. The data throughput is independent of the round-trip delay, and can reach the theoretical limit of what can be achieved with a retransmission method, that is a data throughput of 1-FER, where FER is Frame Error Rate or Packet Error Rate. However, the selective repeat ARQ method requires extensive storage capability and packet handling at both the source and the destination.
Some communication networks transfer data packets in parallel. These networks subdivide the communication link into a number of subchannels for parallel transmission of data packets. In order to guarantee proper ordering of data packets arriving from various subchannels, most conventional networks employ the numbered ARQ method. One conventional network, however, uses the unnumbered ARQ method for transfer of data packets in parallel. This network, which is used by ARPANET and is described by D. Bertsekas and R. Gallager, "Data Networks," 2nd Edition, Prentice Hall International, Inc., London, 1992, applies independent stop-and-wait ARQ methods on eight (virtual) channels in parallel. The data packets are multiplexed over the channels according to availability to transmit a new data packet on the channels. Each data packet contains a virtual channel number identifying the channel on which the data packet is transmitted. As a consequence, the data packets can be transmitted out of order, because the stop-and-wait ARQ method on the separate channels are independent of each other. In other words, retransmissions on one channel will not affect the other channels, but will result in data packets arriving at the destination out of order. As a result, packet numbers at higher protocol layers as required to provide enabling instructions to the destination to properly, reorder the data packets. This method, therefore, requires complicated data-packet reordering overhead, which must be implemented in higher protocol layers.
Therefore, there exists a need for a data communication network with high data throughput which is simple to implement and does not retransmit successfully received data packets unnecessarily.